# --coding:utf-8--
import random
import math


# 模N大数的幂乘的快速算法
# def fastExpMod(b, e, m):  # 底数，幂，大数N
#     result = 1
#     e = int(e)
#     while e != 0:
#         if e % 2 != 0:  # 按位与
#             e -= 1
#             result = (result * b) % m
#             continue
#         e >>= 1
#         b = (b * b) % m
#     return result
# 测试案例
# c = fastExpMod(3,22,12)
# print(c) 9


# 针对随机取得p，q两个数的素性检测
def miller_rabin_test(n):  # p为要检验得数
    p = n - 1
    r = 0
    # P110定理5.17 P108定理5.3.6
    # 寻找满足n-1 = 2^s  * m 的s,m两个数
    #  n -1 = 2^r * p
    while p % 2 == 0:  # 最后得到为奇数的p(即m)
        r += 1
        p /= 2
    b = random.randint(2, n - 2)  # 随机取b=（0.n）
    # 如果情况1    b得p次方  与1  同余  mod n
    if pow(b, int(p), n) == 1:
        return True  # 通过测试,可能为素数
    # 情况2  b得（2^r  *p）次方  与-1 (n-1) 同余  mod n
    for i in range(0, 7):  # 检验六次
        if pow(b, (2 ** i) * int(p), n) == n - 1:
            return True  # 如果该数可能为素数，
    return False  # 不可能是素数


# 生成大素数：
def create_prime_num(keylength):  # 为了确保两素数乘积n  长度不会太长，使用keylength/2
    small_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                    103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
                    211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
                    331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
                    449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577,
                    587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
                    709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
                    853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983,
                    991, 997]
    while True:
        n = random.randrange(2 ** (keylength - 1), 2 ** keylength)
        found = True
        if n in small_primes:
            return n
        for prime in small_primes:
            if n % prime == 0:
                found = False
                break
        if found:
            for i in range(0, 10):
                if miller_rabin_test(n):
                    pass
                else:
                    found = False
                    break
        if found:
            return n


# 生成密钥（包括公钥和私钥）
def create_keys(keylength):  # 公钥是n,e 私钥是n,d
    p = create_prime_num(keylength)
    print('p--', p)
    q = create_prime_num(keylength)
    print('q--', q)
    n = p * q
    print('n--', n)
    # euler函数值
    fn = (p - 1) * (q - 1)
    print('fn--', fn)
    e = selectE(fn, keylength)
    print('pubkey--', e)
    d = match_d(e, fn)
    print('privkey--', d)
    return (n, e, d)


# 随机在（1，fn）选择一个E，  满足gcd（e,fn）=1
def selectE(fn, halfkeyLength):
    while True:
        # e 和 fn 互素
        e = random.randint(0, fn)
        if math.gcd(e, fn) == 1:
            return e


# 根据选择的e，匹配出唯一的d
def match_d(e, fn):
    d = 1
    while True:
        if (e * d) % fn == 1:
            return d
        d += 1


def encrypt(M, e, n):
    return pow(M, e, n)


def decrypt(C, d, m):
    return pow(C, d, m)


def message_encryption(Message ,e ,n):
    s = []
    for ch in Message:
        c = (encrypt(ord(ch), e, n))
        s.append(str(c))
    res = '|'.join(s)
    # print("Encrypt Done!")
    return res


def message_decryption(Cipher, d, n):
    mess = [int(x) for x in Cipher.split('|')]
    print(mess)
    s = ''
    for ch in mess:
        c = chr(decrypt(ch, d, n))
        s += c
    print("Decrypt Done!")
    return s


class USR():
    def __init__(self):
        res = create_keys(12)
        self.pubkey = res[1]
        self.privkey = res[2]
        self.n = res[0]

# usr = USR()
# print(usr.pubkey, usr.privkey, usr.n)
